package Lecture9;

import java.util.Arrays;

public class merge {

	public static void main(String[] args)
	{
		int[] array = { 1,3,2,4,5,7,6,8,9,11,10};
		System.out.println(Arrays.toString(array));
		array = sortMerge(array);
		System.out.println(Arrays.toString(array));
	}

	
	public static int[] sortMerge( int[] array)
	{
		
		if (array.length > 1)
		{
			int a = array.length / 2;
			int b = array.length - a;
			
			int[] first = new int[a];
			int[] second = new int[b];
				
				for(int i = 0; i < a; i++)
				{
					first[i] = array[i];
				}
				
				for(int i = a; i < array.length; i++)
				{
					second[i-a] = array[i];
				}
	
			first = sortMerge(first);
			second = sortMerge(second);
			
			
			int i = 0, j = 0, k = 0;
			
			
			while( a != j && b != k)
			{
				if(first[j] < second[k])
				{
					array[i] = first[j];
					j++;
					i++;
				}
				else
				{
					array[i] = second[k];
					k++;
					i++;
				}
			}
			
			while (a != j)
			{
				array[i] = first[j];
				i++;
				j++;
			}
			
			while (b != k)
			{
				array[i] = second[k];
				i++;
				k++;
			}
				
			
	
		}
		return array;
	}
	
	
	
	
	
	
}
